ডাইজকস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm) একটি পরিচিত গ্রাফ অ্যালগরিদম যা একটি গ্রাফের উত্স (source) থেকে সকল নোডের মধ্যে সর্বনিম্ন (minimum) ওজনের পথ খুঁজে বের করতে ব্যবহৃত হয়। এটি সাধারণত গতি, দূরত্ব বা অন্য কোন মেট্রিককে ভিত্তি করে সবচেয়ে কম খরচে যাওয়ার জন্য পথ নির্ধারণ করে।
অ্যালগরিদমের কাজের পদ্ধতি
নোডগুলির অবস্থান: অ্যালগরিদমটি একটি গ্রাফের নোডগুলির অবস্থানকে নির্ধারণ করে এবং একটি নোডের জন্য দূরত্ব মান শূন্য সেট করে।
এডজেসেন্ট নোড: প্রত্যেকটি নোডের জন্য, সেখান থেকে অ্যাক্সেসযোগ্য নোডগুলির (adjacent nodes) জন্য সম্ভাব্য সর্বনিম্ন দূরত্ব নির্ণয় করা হয়।
চয়ন এবং আপডেট: অ্যালগরিদমটি নিকটবর্তী নোডগুলি চয়ন করে এবং তাদের জন্য নতুন দূরত্ব মান আপডেট করে। যদি একটি নোডের নতুন দূরত্ব বর্তমান দূরত্বের চেয়ে ছোট হয়, তাহলে সেটি আপডেট করা হয়।
ফাইনালাইজেশন: যতক্ষণ না সকল নোডের জন্য সর্বনিম্ন পথ নির্ধারণ করা হয়, অ্যালগরিদমটি চলতে থাকে।
অ্যালগরিদমের পদক্ষেপ
- উত্স নোডের জন্য দূরত্ব মান শূন্য সেট করুন এবং অন্য সকল নোডের জন্য অসীম (∞) সেট করুন।
- একটি সেট তৈরি করুন (যা প্রক্রিয়াকৃত নোডগুলি ধারণ করবে) এবং এটি খালি রাখুন।
- প্রতিটি নোডের জন্য, নিকটতম নোডের দূরত্ব খুঁজে বের করুন।
- নিকটতম নোডটি প্রসেস করুন এবং প্রান্তগুলি (edges) পরীক্ষা করুন, এবং এর নিকটবর্তী নোডগুলির জন্য নতুন দূরত্ব মান আপডেট করুন।
- এই প্রক্রিয়া চলতে থাকে যতক্ষণ না সমস্ত নোড প্রক্রিয়া করা হয়।
উদাহরণ (পাইথনে)
import heapq
def dijkstra(graph, start):
# সর্বনিম্ন দূরত্বের জন্য ডিকশনারি
distances = {node: float('infinity') for node in graph}
distances[start] = 0 # উত্সের দূরত্ব শূন্য
# Priority Queue ব্যবহার করে
priority_queue = [(0, start)] # (দূরত্ব, নোড)
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# যদি বর্তমান দূরত্ব বর্তমান দূরত্বের চেয়ে বড় হয়
if current_distance > distances[current_node]:
continue
# নিকটবর্তী নোডগুলির জন্য দূরত্ব আপডেট করা
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# যদি নতুন দূরত্ব পুরনো দূরত্বের চেয়ে কম হয়
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# গ্রাফের উদাহরণ
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
# অ্যালগরিদম চালানো
distances = dijkstra(graph, 'A')
print(distances) # আউটপুট: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
সময় জটিলতা
- সময় জটিলতা: O((V + E) log V), যেখানে VV হল নোডের সংখ্যা এবং EE হল প্রান্তের সংখ্যা। যদি হিপ ডেটা স্ট্রাকচার ব্যবহার করা হয়, তাহলে এটি দ্রুত কাজ করে।
উপসংহার
ডাইজকস্ট্রা অ্যালগরিদম একটি শক্তিশালী এবং জনপ্রিয় অ্যালগরিদম যা নেটওয়ার্কে এবং গ্রাফে সর্বনিম্ন পথ খুঁজে বের করতে ব্যবহৃত হয়। এটি রাস্তাঘাটের নেভিগেশন, কম্পিউটার নেটওয়ার্ক এবং গ্রাফের জটিল সমস্যাগুলির সমাধানে অত্যন্ত কার্যকর।
